package org.raymond.iworks.study.basic.algorithm.sort;

/**
 * 插入排序:
 * 对欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的
 * 思路:
 * 把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中
 * 包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的
 * 排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表
 * 思路图,括号里是有序表,括号外是无序表:
 * init: (17) 3 25 14 20 9
 * step1: (3 17) 25 14 20 9
 * step2: (3 17 25) 14 20 9
 * step3: (3 14 17 25) 20 9
 * step4: (3 14 17 20 25) 9
 * step5: (3 9 14 17 20 25)
 *
 * init: 3, 9, -1, 10, -2
 * 第1轮排序:
 * 1) 将3作为有序表中的唯一一个元素, 将9,-1,10,2作为无序表中n-1个元素, 得 (3), 9, -1, 10, -2
 * 2) 从无序表中取出第1个元素9, 从后向前遍历有序表, 比较9与3, 9>3, 因此9插入有序表尾部, 得: (3, 9), -1, 10, -2
 * 3) 从无序表中取出第2个元素-1,从后向前遍历有序表,
 * 比较-1与9, -1<9, 遍历到有序表倒数第2个元素3, 比较-1与3, -1<3, 3已经是最前一个元素, 因此-1应插入3的前面, 得: (-1, 3, 9), 10, -2
 * 4) 从无序表中取出第3个元素10,从后向前遍历有序表,
 * 比较10与9, 10>9, 因此10应插入有序表的尾部, 得: (-1, 3, 9, 10), -2
 * 5) 从无序表中取出第4个元素-2,从后向前遍历有序表,
 * 比较-2与10, -2<10, 遍历到有序表倒数第2个元素9, -2<9, 遍历到有序表倒数第3个元素3, -2<3, 遍历到有序表倒数第4个元素-1, -2<-1,
 * -1已经是最前一个元素, 因此-2应插入-1的前面, 得: (-2, -1, 3, 9, 10)
 */
public class InsertSortTest {
    /**
     * 简单插入排序的问题
     * 当需要插入的数较小时,即将插入的距离离有序表尾部较远时,有序表需要遍历较多的次数,效率较低
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = new int[100000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*100000000);
        }
        //arr = new int[]{3, 9, -1, 10, -2};
        //arr = new int[]{101, 34, 119, 1, -1, 89};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        long start = System.nanoTime();
        test1(arr);
        long end = System.nanoTime();
        //System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 1263979600 纳秒,约1.25秒, 100000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        start = System.nanoTime();
        SelectSortTest.jdkSort(arr);
        end = System.nanoTime();
        // post: 3019400 纳秒, 约3毫秒, 100000个元素的数组
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }

    public static void test1(int[] arr){
        // 初始时,arr[0]为有序表, arr[1]~arr[n-1]为无序表
        // 从无序表中向后遍历元素出来,插入到有序表中
        for(int i=1; i<arr.length; i++) {
            // 无序表头,待插入的元素
            int disorderedHead = arr[i];
            int orderIdx=i-1;
            // 从尾向头遍历有序表,比较有序表元素与无序表头的大小
            for(; orderIdx>=0 && disorderedHead<arr[orderIdx]; orderIdx--){
                // 无序表头小于有序表元素,则当前有序表元素后移,为无序表头空出位置
                arr[orderIdx+1]=arr[orderIdx];
            }
            /*
            while(orderIdx>=0 && disorderedHead<arr[orderIdx]){
                arr[orderIdx+1]=arr[orderIdx];
                orderIdx--;
            }
             */
            // 循环结束,需要后移的元素已经完成后移,无序表头插入有序表当前位置
            arr[orderIdx+1] = disorderedHead;
            //System.out.printf("第%d轮插入:\n", i);
            //System.out.println(Arrays.toString(arr));
        }
    }
}
